\chapter{Microsoft Accelerator}
Microsoft Accelerator (referred to as Accelerator from here on) was first developed as a research project aiming to create a GPGPU framework for C\#\cite{accelerator}. In the 2nd version, it has turned into a general framework for solving data parallel problems. The current version supports both calculations on the GPU and on multiple processors. Later versions might implement other targets, for example one for FGPAs\cite{acceleratorv2-intro}.

This project primarily investigate the DX9Target of AcceleratorV2, and this chapter will give a quick overview of how Accelerator works as a middle layer between C\# programmers and the GPU.

\section{Accelerator and the GPU}
Accelerators DirectX9 target solves data-problems by translating the data into textures, and operations into texture shaders. This allows us to do calculations on the GPU. The procedure for translating the function and data in Accelerator is described in "Introduction to Accelerator"\cite{acceleratorv2-intro}:

\begin{enumerate}
\item Translate the processing \emph{code} into a form suitable for a GPU by converting it to a DirectX 9 pixel shader.
\item Translate the \emph{data} into a format that is suitable for the processor by converting it to a DirectX 9 texture.
\item Transfer the shader and textures to the processor and run the operation.
DirectX 9 and the associated drivers partition the data and schedule execution on the various pixel shaders. With other processors, your application might have to handle some or all of these tasks.
\item When the operation is complete, retrieve the texture containing the results and convert it back to an array.
\end{enumerate}

\section{The C\# interface}
Accelerator works with datatypes called parallel arrays, which are represented in the classes FloatParallelArray (FPA), BoolParallelArray (BPA) and IntParallelArray (IPA). All of these inherit from the class ParallelArray (PA). Operations on parallel arrays are functional in nature with no states or mutable data. They have no side effects, operations do not modify arguments, and results are returned in new arrays.

\subsection{Operations}
Before we go further we need to quickly classify operation types. Accelerator classifies operations in six different categories. These are described in "Introduction to Accelerator"\cite{acceleratorv2-intro}:
\begin{itemize}
\item \textbf{Construction} The framework provides methods for creating parallel arrays from \keyword{System.Array} that contains the same elements.
\item \textbf{Conversion} It also provides methods for converting the parallel array result back into the \keyword{System.Array} type.
\item \textbf{Element-wise operations} Most operations are element-wise taking fx the add operation. It takes the n'th element of the first array and adds it with the nth element of the second array, resulting in a new array of the same size.
\item \textbf{Reductions} Reduction operations are operations that reduce the size of the array. A sum operation of a \textit{n X m} array may compute the sum of each row and return a \textit{1 X m} array, or it even compute the sum of all values and return a \textit{1 X 1} array.
\item \textbf{Transformations} Operations that transform the organization of the elements, such as matrix transpose.
\item \textbf{Linear algebra} Accelerator provides binary matrix operations such as scalar product, matrix multiplication and outer product.
\end{itemize}

\section{Programming}
Accelerator Programmers Guide\cite{acceleratorv2-prog} describes the following as a general procedure for working with Accelerator:

\begin{enumerate}
\item Create input arrays. 
\item Load each array from Step 1 into an Accelerator data-parallel array object. 
\item Process the input data by applying Accelerator operations to the data-parallel array objects. 
\item Evaluate the results of the operation on a target processor, which returns an array containing the processed data. 
\end{enumerate}

All operations, except construction operations, are created by calling static member functions on the \keyword{PA} class. An add operation will created by calling \keyword{PA.Add} and so forth. Creation of parallel arrays with values will be done by creating \keyword{FPA} objects.

The following code (listings \ref{fpa-add}) shows an example where two arrays are created, and using the element-wise \keyword{Add} operation, we add each element in each array together and return them in the result array.

\begin{lstlisting}[caption=Accelerator code for addition ,label=fpa-add, language=CSharp]
float[] AddTwoNumbers(float[] x, float[] y) {
	var inputX = new FPA(x);
	var inputY = new FPA(y);
	var add = ParrelelArray.Add(inputX, inputY);
	float[,] result = new float[x.length];
	evalTarget.ToArray(add, out result);
	return result;
}
\end{lstlisting}

The following example  is an implementation of Herons formula to get the area of a triangle, given the three sides.

$s = \frac{a+b+c}{2}$

$A=\sqrt{s(s-a)(s-b)(s-c)}$

The formula can be implemented in Accelerator like this:

\begin{lstlisting}[caption=Herons formula in FPA,label=fpa-heron, language=CSharp]
float[] HeronGPU(float[] x, float[] y, float[] z)
{
	var fpaX = new FPA(x);
	var fpaY = new FPA(y);
	var fpaZ = new FPA(z);
	
	var s = PA.Divide(PA.Add(PA.Add(fpaX, fpaY), fpaZ), 2);
	
	var sX = PA.Subtract(s, fpaX);
	var sY = PA.Subtract(s, fpaY);
	var sZ = PA.Subtract(s, fpaZ);
	
	var area = PA.Sqrt(PA.Multiply(s, PA.Multiply(PA.Multiply(sX, sY), sZ)));

	evalTarget.ToArray(area, out result);
	return result;
}
\end{lstlisting}

Notice in this example (listings \ref{fpa-heron}) that we create only one \keyword{FPA} per float array, and that we reuse these several times while we build up the Accelerator operations. If we created several \keyword{FPA}s, for a single array, we would transfer the data several times. This will become important during the implementation in CoreCalc.

Further, notice that \keyword{PA.Divide} takes both an \keyword{FPA} and an ordinary float. This means that each element in the \keyword{FPA} will be divided by two. Most element-wise functions allow us to do this. 

\section{Other findings}
While working with Accelerator, we have noticed some behavior that is worth mentioning.

\subsection{Behavior of booleans}
Creating BPAs from booleans and working logically with these seems to generate some puzzling results. Consider the following code:

\begin{lstlisting}[caption=Booleans in Accelerator,label=bpa, language=CSharp]
Target t = new DX9Target();
bool[] x = {false, false, false, false};
bool[] r = new bool[4];
bool[] r2 = new bool[4];
t.ToArray(new BPA(x), out r, ExecutionMode.ExecutionModeNormal);
t.ToArray(PA.Not(new BPA(x)), out r, ExecutionMode.ExecutionModeNormal);
\end{lstlisting}

Executing this (listings \ref{bpa}) and afterwords looking into \keyword{r} will have the value {true, false, false, false} and \keyword{r2} will have the value { false, false, false, false }.

Conditional statements \keyword{PA.Cond(BPA, FPA, FPA)} seem to work as intended in Accelerator, and compare functions \keyword{PA.CompareLessThan(FPA, FPA)} seems also to return true or false as logic would prescribe. Using further logical operations \keyword{PA.Not(FPA)} on a \keyword{BPA} returned by a compare functions also seems to give correct results. Our conclusion is that it is possible to work with conditional statements in Accelerator, however, you should never generate BPAs - instead you should rely on Accelerator to do it for you.

\textbf{Floating point numbers}\\
The Accelerator API works only with floating point numbers of the \keyword{float} type, which is most likely caused by the fact that at the time of writing (and development) of Accelerator most GPUs only supported 32-bit floats. Further, many graphic cards are not IEEE 754-compliant \cite{harrisIEEE} which means that results calculated on the GPU might differ from results calculated on the CPU even when using the same precision. NVIDIA Fermi will in the future support double precision\cite{fermi}.

\textbf{Parameters}\\
Values in FPAs cannot be substituted when the FPA object is first created. This means we cannot build up an expression tree and later substitute the values inside it, which would be ideal for constructing function calls in Accelerator syntax and later substituting parameters. The Accelerator developers may include this feature in the future\cite{acceleratorv2-intro}.

\textbf{Random numbers}\\
Accelerator does not implement any ways to generate random numbers. If random data is needed this has to be generated on the CPU and transferred to the GPU. Future versions of Accelerator are expected to implement this\cite{acceleratorv2-intro}.